package com.ronz.stack;

/**
 * @Description 使用栈实现一个综合计算器，但是运算符只包括 +、-、*、/
 * 如：计算 30+2*6-1=?
 * @Author Ronz
 * @Date 2020/12/27 18:45
 * @Version 1.0
 */
public class No2_Stack_BasicCalculator {

    public static void main(String[] args) {
        String str = "300+20*6-10*1";
        ArrayNumStack numStack = new ArrayNumStack(5);
        ArrayOperStack operStack = new ArrayOperStack(5);

        int num = 0;
        // 具体计算
        int length = str.length();
        for (int index = 0; index < length; index++) {
            char param = str.charAt(index);
            // 判断是不是数字
            if ('0' <= param && param <= '9') {
                // 如果是数字
                num = num * 10 + param - 48;

                // 还需要往后判断一位，看看是数字还是符号，如果是符号就进栈，如果是数字就不急着进栈
                // 但是，需要首先看看后面还有没有数据了
                if (index + 1 < length) {
                    // 如果后面还有数据，就取出来看看是符号还是数字
                    char next = str.charAt(index + 1);
                    if (!(next >= '0' && next <= '9')) {
                        numStack.pushNum(num);
                        // 初始化
                        num = 0;
                    }
                } else {
                    // 如果后面没数据了，说明到了字符串最后了
                    numStack.pushNum(num);
                }
            } else {
                // 如果不是数字，就是符号
                // 如果符号栈为空，直接进栈
                if (operStack.isEmpty()) {
                    operStack.pushOper(param);
                } else {

                    // 符号优先级比较了，用于判断是否做运算
                    // 先判断将要进栈的符号的优先级和栈顶的符号优先级哪个高
                    int pri_param = getPriority(param);
                    int pri_top = getPriority(operStack.peek());
                    if (pri_param >= pri_top) {
                        // 如果要进栈的符号优先级大于等于栈顶的，则直接进栈
                        operStack.pushOper(param);
                    } else {
                        // 如果要进栈的符号优先级小于等于栈顶的，那么栈顶元素出栈进行运算
                        // 符号栈出一个元素
                        char oper = operStack.popOper();
                        // 数字栈出两个元素
                        int num_1 = numStack.popNum();
                        int num_2 = numStack.popNum();
                        int res = calculate(num_1, num_2, oper);
                        // 运算结果进栈
                        numStack.pushNum(res);
                        operStack.pushOper(param);
                    }
                }
            }
        }

        // 经过上面的操作，符号栈剩下的都是优先级相等的符号了，直接出栈做运算就可以啦
        // 如果符号栈为空，说明已经计算完了
        while (!operStack.isEmpty()) {
            char oper = operStack.popOper();
            int num_1 = numStack.popNum();
            int num_2 = numStack.popNum();
            int res = calculate(num_1, num_2, oper);
            numStack.pushNum(res);
        }
        // 这个时候，数字栈的最后一个元素，就是最后的计算结果
        System.out.println(str + " = " + numStack.popNum());
    }


    // 获取运算符优先级，数字越大，优先级越大
    private static int getPriority(char oper) {
        if (oper == '+' || oper == '-') {
            return 0;
        }
        if (oper == '*' || oper == '/') {
            return 1;
        }
        return -1;
    }

    // 给定两个数字以及运算符，计算出结果
    private static int calculate(int num_1, int num_2, char oper) {
        int result = 0;
        switch (oper) {
            case '+':
                result = num_1 + num_2;
                break;
            case '-':
                result = num_2 - num_1;
                break;
            case '*':
                result = num_1 * num_2;
                break;
            case '/':
                result = num_2 / num_1;
            default:
                break;
        }
        return result;
    }

}

/**
 * @Description 使用数组模拟数字栈
 */
class ArrayNumStack {
    private int maxSize;            // 栈的容量
    private int[] numStack;        // 存放数字的栈
    private int top;            // 数字栈的栈顶

    public ArrayNumStack(int maxSize) {
        this.maxSize = maxSize;
        numStack = new int[maxSize];
        top = -1;
    }

    // 数字入栈
    public void pushNum(int num) {
        if (isFull()) {
            System.out.println("数字栈满了！");
            return;
        }
        numStack[++top] = num;
    }

    // 数字出栈
    public int popNum() {
        if (isEmpty()) {
            throw new RuntimeException("数字栈为空！");
        }
        return numStack[top--];
    }

    // 判断数字栈是否满了
    private boolean isFull() {
        return top == maxSize - 1;
    }

    // 判断数字栈是否为空
    private boolean isEmpty() {
        return top == -1;
    }
}

/**
 * @Description 数组模拟运算符栈
 */
class ArrayOperStack {
    private int maxSize;    // 运算符栈的大小
    private char[] operStack;   // 模拟运算符栈
    private int top;        // 栈顶指针

    public ArrayOperStack(int maxSize) {
        this.maxSize = maxSize;
        operStack = new char[maxSize];
        top = -1;
    }

    // 看一下运算符栈栈顶元素是什么，用于比较运算符优先级
    public char peek() {
        return operStack[top];
    }

    // 运算符入栈
    public void pushOper(char val) {
        if (isFull()) {
            System.out.println("运算符栈满了！");
            return;
        }
        operStack[++top] = val;
    }

    // 运算符出栈
    public char popOper() {
        if (isEmpty()) {
            throw new RuntimeException("运算符栈为空！");
        }
        return operStack[top--];
    }

    // 判断运算符栈是否满了
    private boolean isFull() {
        return top == maxSize - 1;
    }

    // 判断运算符栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }
}
